﻿//AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的左右⼦树都是AV树，且左右⼦树的⾼度差的绝对值不超过1。
//AVL树是⼀颗⾼度平衡搜索⼆叉树，通过控制⾼度差去控制平衡
//AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念，每个结点都有⼀个平衡因⼦，任何
//结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0 / 1 / -1，
//AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 ，那么增删查改的效率也可以控制在O(logN)

//旋转的原则
//1. 保持搜索树的规则
//2. 让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度
//旋转总共分为四种，左单旋 / 右单旋 / 左右双旋 / 右左双旋。

